package stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 394.字符串解码
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 */
public class decodeString {
    /**
     * hot100一刷
     * hot100二刷
     */
    public String decodeString(String s) {
        Deque<Integer> stack_num = new LinkedList<>(); // 存储需要重复字符串的数字
        Deque<String> stack_res = new LinkedList<>(); // 存储待重复的字符串
        StringBuilder res = new StringBuilder();
        int num = 0;

        for (Character x : s.toCharArray()) {
            if (x == '[') {
                stack_num.push(num); // 把括号前的数字压栈
                stack_res.push(res.toString()); //把括号前的字母——即将来等待被重复的字符串压栈
                //需重复数字归零（注意！因为 num 可能会是n位数，为了方便后续统一x10处理，必须归零
                num = 0;
                res = new StringBuilder(); // res 也要重置
            } else if (x == ']') {
                int cur_num = stack_num.pop();  //此次要重复的次数数字
                String last_res = stack_res.pop();  //紧贴着这一组括号外的还没执行重复的字符串
                StringBuilder tmp = new StringBuilder(); // 本次要重复的完整子串
                for (int i = 0; i < cur_num; i++)
                    tmp.append(res);
                res = new StringBuilder(last_res + tmp);
            } else if (x >= '0' && x <= '9')
                num = num * 10 + (x - '0'); // 把字符数字转换为数字
            else
                res.append(x);
        }

        return res.toString();
    }



}
